/**
 * Tree2-3-4树
 * 详细参考：http://www.cnblogs.com/fireway/p/8071978.html
 *
 * @author fireway
 */
class DataItem {
    public long mData;

    public DataItem(long date) {
        mData = date;
    }

    /**
     * display item, format "/27"
     */
    public void display() {
        System.out.print("/" + mData);
    }
}

class Node {
    private static final int ORDER = 4;

    // 当前数据项的个数
    private int mDataItemSize;

    // 父节点
    private Node mParent;

    // 子节点
    private Node[] mChildrent = new Node[ORDER];

    // mDataItems中的数据项组成了一个有序数组。
    // 插入新数据项或删除原来的数据项时，它们还必须继续保持有序的状态。
    // 数据项需要移位腾出空间来按序插入新数据项，或在删除某个数据项后，
    // 往前移以补上空着的数据单元。
    private DataItem[] mDataItems = new DataItem[ORDER - 1];

    public void connectChild(int childNum, Node child) {
        mChildrent[childNum] = child;
        if (child != null) {
            child.mParent = this;
        }
    }

    public Node disconnectChild(int childNum) {
        Node temp = mChildrent[childNum];
        mChildrent[childNum] = null;
        return temp;
    }

    public Node getChild(int childNum) {
        return mChildrent[childNum];
    }

    public Node getParent() {
        return mParent;
    }

    public boolean isLeaf() {
        return null == mChildrent[0];
    }

    public int getDataItemSize() {
        return mDataItemSize;
    }

    public DataItem getDataItem(int index) {
        return mDataItems[index];
    }

    public boolean isFull() {
        return (mDataItems.length == mDataItemSize);
    }

    public int findDataItem(long key) {
        return -1;
    }

    /**
     * return index to the new item
     */
    public int insertDataItem(DataItem dataItem) {
        mDataItemSize++;
        // assumes node is not full
        // 从最右边开始
        for (int i = mDataItems.length -1; i >= 0; i--) {
            if (mDataItems[i] == null) {
                continue;
            } else {
                // 如果当前i的元素值大，让它往右移动
                if (dataItem.mData < mDataItems[i].mData) {
                    mDataItems[i + 1] = mDataItems[i];
                } else {
                    mDataItems[i + 1] = dataItem;
                    return i + 1;
                }
            }

        }
        mDataItems[0] = dataItem;
        return 0;
    }

    /**
     * 删除数据项
     */
    public DataItem removeDataItem() {
        DataItem temp = mDataItems[mDataItemSize - 1];
        mDataItems[mDataItemSize - 1] = null;
        mDataItemSize--;
        return temp;
    }

    /**
     * format "/24/56/74/"
     */
    public void displayNode() {
        for (int i = 0; i < mDataItemSize; i++) {
            mDataItems[i].display();
        }
        System.out.println("/");
    }
}

/**
 * 2-3-4 树
 *
 * @author fireway
 */
public class Tree234 {
    private Node mRoot = new Node();

    public int find(long key) {
        return -1;
    }

    public void insert(long value) {
        Node current = mRoot;
        DataItem dataItem = new DataItem(value);

        while (true) {
            if (current.isFull()) {
                split(current);
                current = current.getParent();
                current = getNextChild(current, value);
            } else if (current.isLeaf()) {  // 增加元素总是插入叶子节点中
                break;
            } else {
                current = getNextChild(current, value);
            }
        }

        current.insertDataItem(dataItem);
    }

    public void split(Node current) {
        // assumes node is full
        DataItem dataItemB = null, dataItemC = null;
        Node parent = null, child2 = null, child3 = null;

        dataItemC = current.removeDataItem();
        dataItemB = current.removeDataItem();

        child2 = current.disconnectChild(2);
        child3 = current.disconnectChild(3);

        Node right = new Node();

        if (current == mRoot) {
            mRoot = new Node();
            parent = mRoot;
            mRoot.connectChild(0, current);
        } else {
            parent = current.getParent();
        }

        // item B to parent
        int itemIndex = parent.insertDataItem(dataItemB);
        for (int i = parent.getDataItemSize() - 1; i > itemIndex; i--) {
            Node temp = parent.disconnectChild(i);
            parent.connectChild(i+1, temp);
        }

        // connect right to parent
        parent.connectChild(itemIndex + 1, right);

        // deal with right
        right.insertDataItem(dataItemC);
        right.connectChild(0, child2);
        right.connectChild(1, child3);
    }

    /**
     * gets appropriate child of node during search for value
     */
    public Node getNextChild(Node current, long value) {
        // assumes node is not empty, not full, not a leaf
        int i = 0;
        for (i = 0; i < current.getDataItemSize(); i++) {
            if (value < current.getDataItem(i).mData) {
                return current.getChild(i);
            }
        }
        return current.getChild(i);
    }

    public void displayTree() {
        recDisplayTree(mRoot, 0, 0);
    }

    private void recDisplayTree(Node node, int level, int childNumber) {
        System.out.print("level=" + level + " child=" + childNumber + " ");
        node.displayNode();

        // call ourselves for each child of this node
        for (int i = 0; i < node.getDataItemSize() + 1; i++) {
            Node nextNode = node.getChild(i);
            if (nextNode != null) {
                recDisplayTree(nextNode, level + 1, i);
            } else {
                return;
            }
        }
    }
}

